# -*- coding: utf-8 -*-

"""剑指 Offer II 020. 回文子字符串的个数
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：
1 <= s.length <= 1000
s 由小写英文字母组成"""


class Solution:
    """本例的解法是从示例中得到启发，从头到尾扫描字符串，每扫描到一个地方作为回文中心，向左右两侧扩展，寻找回文子串"""
    def countSubstrings(self, s: str) -> int:
        idx, last = [], len(s)-1
        for i in range(last):
            idx.append(i)
            idx.append(i+0.5)
        idx.append(last)

        count = 0
        for i in idx:
            try:
                if type(i) is int:
                    count += 1
                    left, right = i-1, i+1
                else:
                    left, right = int(i-0.5), int(i+0.5)
                
                while True:
                    if left < 0 or right > last:
                        break

                    if s[left] == s[right]:
                        count += 1
                        left -= 1
                        right += 1
                    else:
                        break
            except IndexError:
                continue
        
        return count


if __name__ == '__main__':
    so = Solution()
    print(so.countSubstrings('abc'))
    print(so.countSubstrings('aaa'))

